package com.example.doublepointer;

/**
 * 面试题 17.21. 直方图的水量
 * 给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
 * <p>
 * <p>
 * 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。
 * <p>
 * 示例:
 * <p>
 * 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出: 6
 * <p>
 * <p>
 * 思路：双指针
 * 维护一个左右边界的双指针left，tight。
 * 维护一个左边最大值leftMax和右边最大值rightMax
 * 当左边界小于右边界时
 * 首先我们更新一下左右的最大值。
 * 接着如果左边当前值小于右边当前值（这一条件就控制了如果某一边的值一直是大的，那永远走的是另一边，也就不会算超了）。我们就走左边（因为水量是由最低的边界来确定的）.总之哪边小就走那边，并且将边界值向中心移。
 * 用左边最大值-左边当前值。（注意：只有开头和结尾都为0时才存不住水，这种情况已经通过“左边最大值-左边当前值”抵消了，包括左右的第一个柱子也会自我抵消）
 */
public class VolumeOfHistogramLCCI {
    public static void main(String[] args) {
        VolumeOfHistogramLCCI volumeOfHistogramLCCI = new VolumeOfHistogramLCCI();
        int[] height = new int[]{10, 0, 0, 1, 1};
        System.out.println(volumeOfHistogramLCCI.trap(height));
    }

    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
}
